package com.hl.algor_data_struct.sort;

/**
 * Created by yuanhailong on 2021/10/24.
 * 归并排序
 *     1）将数组划分成2部分，左边部分和右边部分
 *     2） 先将左边部分排序，然后将右边部分排序
 *     3） 将左右边排序号的数据写入到一个辅助空间中，让其整体排序
 *     4） 将整体排好序的数据拷贝到原始数组中
 *
 *
 *     时间复杂度O(N*logN)   额外空间复杂度O(N)
 */
public class MegerSort {



    public static void megerSort(int[] arr,int L,int R){
        if(L==R){
            return;
        }
        //找到中间位置
        int mid=L+((R-L)>>1);
        megerSort(arr,L,mid);
        megerSort(arr,mid+1,R);
        meger(arr,L,mid,R);
    }
    private static void meger(int arr[],int L,int M,int R){
        int[] help=new int[SortConstants.sortArr.length];
        System.out.println("meger");
        int i=0;
        int p1=L;
        int p2=R;

        while(p1<=M && p2<=R){
            help[i++]=arr[p1]<=arr[p2]?arr[p1++]:arr[p2++];
        }
        while(p1<=M){
            help[i++]=arr[p1++];
        }
        while(p2<=R){
            help[i++]=arr[p2++];
        }
        //拷贝到原始数组
        for(i=0;i<help.length;i++){
            arr[L+i]=help[i];
        }

    }



    public static void main(String[] args) {
        megerSort(SortConstants.sortArr,0,SortConstants.sortArr.length-1);
        for(int num:SortConstants.sortArr){
            System.out.println(num);
        }
    }

}
